Nội dung thuật toán
Cho G = (V,E) là đồ thị có tập các đỉnh V và tập các cạnh E. v là một đỉnh trong V va u là đỉnh kề của v, sao cho u cũng thuộc V. Khi đó ta dán nhãn cho tất cả các đỉnh của đồ thị là 0. Chọn một đỉnh v thuộc tập V để bắt đầu duyệt. Gán nhãn đỉnh v này la 1-v đã được duyệt. Chọn đỉnh u trong tập V kề với đỉnh v mà nhãn là 0. Duyệt qua đỉnh u và gán nhãn u là 1. Tiếp tục quá trình duyệt đến khi tất cả các đỉnh đồ thị có nhãn là 1.
Ví dụ áp dụng
=(V,E) có V={1,2,3,4,5} được lưu vào bảng như sau:
do thi goc
Đỉnh | Các đỉnh kề |
---|
1 | 2,3,4,5 |
2 | 1,3,4,5 |
3 | 1,2 |
4 | 1,2,5 |
5 | 1,2,4 |
Trước tiên, ta gán nhãn tất cả các đỉnh là 0 (chưa duyệt). Khi đỉnh nào được duyệt qua thì ta cập nhật lại nhãn cho đỉnh đó là 1.
- Các bước duyệt theo chiều sâu:
Chọn một đỉnh từ danh sách các đỉnh của G. Ở đây ta chọn đỉnh 2 làm đỉnh đầu tiên để bắt đầu duyệt.
Thực hiện DFS(2):pro
dothi2
Đỉnh | Các đỉnh kề | Nhãn |
---|
1 | 2,3,4,5 | 0 |
2 | 1, 3,4,5 | 1 |
3 | 1,2 | 0 |
4 | 1,2,5 | 0 |
5 | 1,2,4 | 0 |
Gán nhãn cho đỉnh 2 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 2 có đỉnh 3 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 3.
Thực hiện DFS(3):
Duyet_dinh3
Đỉnh | Các đỉnh kề | Nhãn |
---|
1 | 2,3,4,5 | 0 |
2 | 3,4,5 | 1 |
3 | 1,2 | 1 |
4 | 1,2,5 | 0 |
5 | 1,2,4 | 0 |
Gán nhãn cho đỉnh 3 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 3 có đỉnh 1 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 1.
Thực hiện DFS(1):
Duyet_dinh1
Đỉnh | Các đỉnh kề | Nhãn |
---|
1 | 2,3,4,5 | 1 |
2 | 3,4,5 | 1 |
3 | 1,2 | 1 |
4 | 1,2,5 | 0 |
5 | 1,2,4 | 0 |
Gán nhãn cho đỉnh 1 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 1 có đỉnh 4 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 4.
Thực hiện DFS(4):
Duyet_dinh4
Đỉnh | Các đỉnh kề | Nhãn |
---|
1 | 2,3,4,5 | 1 |
2 | 3,4,5 | 1 |
3 | 1,2 | 1 |
4 | 1,2,5 | 1 |
5 | 1,2,4 | 0 |
Gán nhãn cho đỉnh 4 là 1 khi duyệt qua nó, tìm thấy các đỉnh kề của đỉnh 4 có đỉnh 5 có nhãn là 0(chưa được duyệt).Lặp lại quá trình với đỉnh 5.Đến đây, tất cả các đỉnh đã duyệt qua nên ta dừng thuật toán. Xuất ra dãy các đỉnh đã duyệt như sau: 2,3,1,4,5.